import java.util.*;


public class Heap<Tipo>{
	
	protected Vector<Tipo> data;
	private Comparator<Tipo> comp;
	
	public Heap(Comparator<Tipo> comp){
		
		data= new Vector<Tipo>();
		this.comp=comp;
	}
	
	
	
	/**
	 * pre: 0 = i >size
	 * post: returns parent
	 */
	private static int padre(int x){
		return (x-1)/2;
	}
	
	/**
	 *
	 *
	 */
	private static int left(int x){
		return 2*x+1;
	}
	/**
	 *
	 *
	 */
	protected static int right(int i)
	{
		return 2*(i+1);
	}

	/**
	 *
	 *
	 */
	private void filtrar(int hoja){
		int parent = padre(hoja);
		Tipo valor = data.get(hoja);
		while(hoja > 0 && ( comp.compare(valor, data.get(parent))<0)){
			data.set(hoja,data.get(parent));
			hoja = parent;
			parent = padre(hoja);
		}
		data.set(hoja, valor);
	}
	
	/**
	 *
	 *
	 */
	public void add(Tipo dato){
		data.add(dato);
		filtrar(data.size()-1);
	}
	/**
	 *
	 *
	 */
	protected void pushDownRoot(int root)


	{
		int heapSize = data.size();
		Tipo value = data.get(root);
		
		while (root < heapSize) 
		{
			int childpos = left(root);
			
			if (childpos < heapSize)
			{
				if ((right(root) < heapSize) &&(comp.compare(data.get(childpos+1), data.get(childpos)) < 0))
				{
					childpos++;
				}

				if (comp.compare(data.get(childpos), value)<0)
				{
					data.set(root,data.get(childpos));
					root = childpos;
				}else 
				{
					data.set(root,value);
					return;
				}
			} else
			{
				data.set(root, value);
				return;
			}
		}
	}

	/**
	 *
	 *
	 */
	public Tipo remove()

	{
		Tipo minVal = getFirst();
		data.set(0,data.get(data.size()-1));
		data.setSize(data.size()-1);
		if (data.size() > 1) pushDownRoot(0);
		return minVal;
	}

	/**
	 *
	 *
	 */
	public Tipo getFirst(){
		return data.get(0);
	}
	public Tipo get(int a){
		return data.get(a);
	}
	public int size(){
		return data.size();
	}
	public boolean isEmpty(){
		return data.size()==0;
	}

	
	
	
}